package com.ssy.lingxi.platform.manage.util;

import java.util.*;

/**
 * ac字典树
 * @author yzc
 * @version 2.0.0
 * @date 2020/11/19
 */
public class TrieTree {
    /**
     * 所有模式串的首字符节点
     */
    private TrieNode[] firstNodes = new TrieNode[Character.MAX_VALUE + 1];
    /**
     * 模式串数组
     */
    private String[] keywords;

    /**
     * 初始化字典树
     *
     * @param keywords 关键字列表
     */
    public void init(Collection<String> keywords) {
        this.keywords = new String[keywords.size()];
        this.keywords = keywords.toArray(this.keywords);

        // 根节点
        AcTrieNode root = new AcTrieNode();

        // 构建层次节点映射
        Map<Integer, List<AcTrieNode>> allNodeLayers = buildLayerNodeMap(root);

        // 构建所有节点集合
        List<AcTrieNode> allNodeList = buildAllNodeList(root, allNodeLayers);

        // 清空层次节点映射
        allNodeLayers.clear();

        // 构建失败回溯指针
        buildFailNode(root, allNodeList);

        // 构建字典树
        List<TrieNode> trieNodeList = buildTrieTree(root, allNodeList);

        // 清空所有节点映射
        allNodeList.clear();

        // 缓存所有模式串首字符节点
        buildFirstNodes(trieNodeList);
    }

    // =======================================公共方法=======================================

    /**
     * 在文本中查找第一个关键字
     * keyword:["a", "b", "c"]
     * text: abcd ->  a
     * text: cbda ->  c
     * @param text 文本
     * @return 查找到的关键字
     */
    public String findFirst(final String text) {
        // 当前匹配到的节点
        TrieNode ptr = null;
        final List<String> list = new ArrayList<>();

        // 遍历文本
        for (int i = 0; i < text.length(); i++) {
            // 文本的字符
            final char t = text.charAt(i);

            TrieNode tn = null;
            if (ptr == null) {
                // 当前节点为空,则从模式串首字符节点中查询
                tn = firstNodes[t];
            } else {
                // 当前节点不为空,则从节点的子节点中查询
                if (!ptr.hasKey(t)) {
                    // 子节点中没有,则再从模式串首字符节点中查询
                    tn = firstNodes[t];
                } else {
                    // 子节点中有该字符
                    tn = ptr.getValue(t);
                }
            }

            if (tn != null && tn.end) {
                // 如果该节点是模式串的未节点,获取匹配到的keyword
                return keywords[tn.results.get(0)];
            }

            ptr = tn;
        }
        return null;
    }

    /**
     * 在文本中查找所有的关键字
     * keyword:["a", "b", "c"]
     * text: abcd ->  ["a", "b", "c"]
     * text: cbda ->  ["c", "b", "a"]
     * @param text 文本
     * @return 查找到的关键字集合
     */
    public List<String> findAll(final String text) {
        // 当前匹配到的节点
        TrieNode ptr = null;
        final List<String> list = new ArrayList<>();

        // 遍历文本
        for (int i = 0; i < text.length(); i++) {
            // 文本的字符
            final char t = text.charAt(i);

            TrieNode tn = null;
            if (ptr == null) {
                // 当前节点为空,则从模式串首字符节点中查询
                tn = firstNodes[t];
            } else {
                // 当前节点不为空,则从节点的子节点中查询
                if (!ptr.hasKey(t)) {
                    // 子节点中没有,则再从模式串首字符节点中查询
                    tn = firstNodes[t];
                } else {
                    // 子节点中有该字符
                    tn = ptr.getValue(t);
                }
            }

            if (tn != null && tn.end) {
                // 如果该节点是模式串的未节点,获取匹配到的keyword
                tn.results.forEach(item -> {
                    list.add(keywords[item]);
                });
            }

            ptr = tn;
        }
        return list;
    }

    /**
     * 判断文本是否包含关键字
     * keyword:["a", "b", "c"]
     * text: abcd ->  true
     * text: def ->  false
     * @param text 文本
     * @return true, false
     */
    public boolean containsAny(final String text) {
        // 当前匹配到的节点
        TrieNode ptr = null;
        final List<String> list = new ArrayList<>();

        // 遍历文本
        for (int i = 0; i < text.length(); i++) {
            // 文本的字符
            final char t = text.charAt(i);

            TrieNode tn = null;
            if (ptr == null) {
                // 当前节点为空,则从模式串首字符节点中查询
                tn = firstNodes[t];
            } else {
                // 当前节点不为空,则从节点的子节点中查询
                if (!ptr.hasKey(t)) {
                    // 子节点中没有,则再从模式串首字符节点中查询
                    tn = firstNodes[t];
                } else {
                    // 子节点中有该字符
                    tn = ptr.getValue(t);
                }
            }

            if (tn != null && tn.end) {
                // 如果该节点是模式串的未节点,获取匹配到的keyword
                return true;
            }

            ptr = tn;
        }
        return false;
    }

    /**
     * 在文本中替换所有的关键字
     * keyword:["a", "b", "c"]
     * replaceChar: "*"
     * text: abcd ->  ***d
     * @param text        文本
     * @param replaceChar 替换符
     * @return 替换后的文本
     */
    public String replace(final String text, final char replaceChar) {
        final StringBuilder result = new StringBuilder(text);
        // 当前匹配到的节点
        TrieNode ptr = null;
        final List<String> list = new ArrayList<>();

        // 遍历文本
        for (int i = 0; i < text.length(); i++) {
            // 文本的字符
            final char t = text.charAt(i);

            TrieNode tn = null;
            if (ptr == null) {
                // 当前节点为空,则从模式串首字符节点中查询
                tn = firstNodes[t];
            } else {
                // 当前节点不为空,则从节点的子节点中查询
                if (!ptr.hasKey(t)) {
                    // 子节点中没有,则再从模式串首字符节点中查询
                    tn = firstNodes[t];
                } else {
                    // 子节点中有该字符
                    tn = ptr.getValue(t);
                }
            }

            if (tn != null && tn.end) {
                // 如果该节点是模式串的未节点,获取匹配到的keyword
                final int maxLength = keywords[tn.results.get(0)].length();
                final int start = i + 1 - maxLength;
                for (int j = start; j <= i; j++) {
                    result.setCharAt(j, replaceChar);
                }
            }

            ptr = tn;
        }
        return result.toString();
    }

    // =======================================私有方法=======================================

    /**
     * 构建层次节点映射
     *
     *  keyword:
     * "ce","bc","bcd","abcd"
     *
     * return:
     *   key   list
     *   1     c b () a
     *   2     e c () b
     *   3     _ _ d c
     *   4     _ _ _ d
     */
    private Map<Integer, List<AcTrieNode>> buildLayerNodeMap(AcTrieNode root) {
        Map<Integer, List<AcTrieNode>> nodeLayerMap = new HashMap<>();
        // 关键词数组遍历
        for (int i = 0; i < keywords.length; i++) {
            String p = keywords[i];
            AcTrieNode nd = root;
            // 关键词遍历
            for (int j = 0; j < p.length(); j++) {
                // 添加子节点并返回
                nd = nd.add(p.charAt(j));

                if (nd.depth == 0) {
                    // 每个关键字符一层,从第一层开始
                    nd.depth = j + 1;
                    // 如果该层已存在list则添加,否则新建list后添加
                    if (!nodeLayerMap.containsKey(nd.depth)) {
                        List<AcTrieNode> nodes = new ArrayList<>();
                        nodes.add(nd);
                        nodeLayerMap.put(nd.depth, nodes);
                    } else {
                        nodeLayerMap.get(nd.depth).add(nd);
                    }
                }
            }
            // 模式串末节点保存keyword索引
            nd.setResults(i);
        }

        return nodeLayerMap;
    }

    /**
     * 构建所有节点集合
     *
     * keyword:
     * "ce","bc","bcd","abcd"
     *
     * layerMap:
     *   key   list
     *   1     c b () a
     *   2     e c () b
     *   3     _ _ d c
     *   4     _ _ _ d
     *
     * return:
     * '', 'c', 'b', 'a', 'e', 'c', 'b', 'd', 'c', 'd'
     */
    private List<AcTrieNode> buildAllNodeList(AcTrieNode root, Map<Integer, List<AcTrieNode>> LayerNodeMap) {
        List<AcTrieNode> allNodeList = new ArrayList<>();
        allNodeList.add(root);
        // 获取每层的节点,并添加到集合中
        for (int i = 0; i < LayerNodeMap.size(); i++) {
            List<AcTrieNode> nodes = LayerNodeMap.get(i + 1);
            allNodeList.addAll(nodes);
        }
        return allNodeList;
    }

    /**
     * 构建失败回溯指针
     * @param root 根节点
     * @param allNode 所有节点
     */
    private void buildFailNode(AcTrieNode root, List<AcTrieNode> allNode) {
        for (int i = 1; i < allNode.size(); i++) {
            // 当前节点
            AcTrieNode node = allNode.get(i);
            // 节点的索引,根节点索引为0
            node.index = i;
            // 父节点的回溯节点
            AcTrieNode rNode = node.parent.fail;
            // 当前节点的字符
            Character c = node.ch;
            // 如果回溯节点不为空,且回溯节点下存在该字符
            while (rNode != null && !rNode.children.containsKey(c)) {
                // 跳转到最上级的回溯节点
                rNode = rNode.fail;
            }

            if (rNode == null) {
                // 如果最上级的回溯节点为空,则回溯节点为根节点
                node.fail = root;
            } else {
                // 如果最上级的回溯节点不为空,记录当前节点的回溯节点
                node.fail = rNode.children.get(c);
                // 复制模式串末尾节点记录keyword的索引
                for (Integer result : node.fail.results) {
                    node.setResults(result);
                }
            }
        }
        root.fail = root;
    }

    /**
     * 构建字典树
     * @param root 根节点
     * @param allNode 所有节点
     * @return 节点集合
     */
    private List<TrieNode> buildTrieTree(AcTrieNode root, List<AcTrieNode> allNode) {
        // 构建新字典树
        List<TrieNode> allNode2 = new ArrayList<>();
        for (int i = 0; i < allNode.size(); i++) {
            allNode2.add(new TrieNode());
        }
        // 拷贝属性
        for (int i = 0; i < allNode2.size(); i++) {
            AcTrieNode oldNode = allNode.get(i);
            // 当前节点
            TrieNode newNode = allNode2.get(i);

            // 子节点复制
            for (Character key : oldNode.children.keySet()) {
                AcTrieNode nd = oldNode.children.get(key);
                // 当前节点的子节点映射, 字符-新节点映射
                newNode.add(key, allNode2.get(nd.index));
            }
            // 复制模式串末尾节点记录keyword的索引
            oldNode.results.forEach(newNode::setResults);

            // 递归所有回溯节点的子节点,也存在当前节点的子节点下
            oldNode = oldNode.fail;
            while (oldNode != root) {
                // 遍历子节点
                for (Character key : oldNode.children.keySet()) {
                    // 子节点
                    AcTrieNode nd = oldNode.children.get(key);
                    // 新节点没有该子节点的key,则保存
                    if (!newNode.hasKey(key)) {
                        newNode.add(key, allNode2.get(nd.index));
                    }
                }

                // 复制模式串末尾节点记录keyword的索引
                oldNode.results.forEach(newNode::setResults);
                oldNode = oldNode.fail;
            }
        }

        return allNode2;
    }

    /**
     * 缓存所有模式串首字符节点
     * @param trieNodeList 节点集合
     */
    private void buildFirstNodes(List<TrieNode> trieNodeList) {
        TrieNode[] first = new TrieNode[Character.MAX_VALUE + 1];
        TrieNode root = trieNodeList.get(0);
        for (Character key : root.children.keySet()) {
            TrieNode nd = root.children.get(key);
            first[(int) key] = nd;
        }
        firstNodes = first;
    }
}